package demo;
import java.util.LinkedList;
import java.util.Queue;
public   class CreateTree {
    //构建一颗二叉树
    public static TreeNode createTree(){
        TreeNode n1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3=new TreeNode(3);
        TreeNode n4=new TreeNode(4);
        TreeNode n5=new TreeNode(5);
        TreeNode n6=new TreeNode(6);
        TreeNode n7=new TreeNode(7);

        n1.left=n2;n1.right=n3;
        n2.left=n4;n2.right=n5;
        n3.left=n6;n3.right=n7;


        return n1;
    }
    //二叉树前序遍历

    public void preTraverdsal(TreeNode root){
        if(root==null){
            return ;
        }
        System.out.print(root.val);
        preTraverdsal(root.left);
        preTraverdsal(root.right);
    }
    //二叉树中序遍历
    public void inorderTraverdsal(TreeNode root){
        if(root==null){
            return ;
        }

        preTraverdsal(root.left);
        System.out.print(root.val);
        preTraverdsal(root.right);
    }
    //二叉树后序遍历

    public void postTraverdsal(TreeNode root){
        if(root==null){
            return ;
        }

        preTraverdsal(root.left);
        preTraverdsal(root.right);
        System.out.print(root.val);
    }

    //求二叉树的结点数(子问题思想)
    public int size1(TreeNode root ){
        if(root==null){
            return 0;
        }
        int leftSize=size1(root.left);//左树结点个数
        int rightSize=size1(root.right);//右树结点个数
        return leftSize+rightSize+1;//左+右+根
    }

    //求二叉树的结点数(遍历思想)
    public static int usedSize;//总结点个数
    public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        usedSize=usedSize+1;//遍历一个结点加1
        size2(root.left);//左树
        size2(root.right);//右树
        return usedSize;//总结点
    }
    //求二叉树的叶子结点个数（子问题思想）
    public int leafSize1(TreeNode root){
        //判断是否是空树
        if(root==null){
            return 0;
        }
        //一棵树左右子树都为空则代表是叶子
        if(root.left==null&&root.right==null){
            return 1;//返回一棵树的叶子
        }
        int left=leafSize1(root.left);//递归求所有左字树的叶子
        int right=leafSize1(root.right);//递归求所有右字树的叶子

        return left+right;//返回左右字树总叶子
    }
    //（遍历思想）求叶子个数
    public static int leaf;
    public int leafSize2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            leaf=leaf+1;
        }
        leafSize2(root.left);
        leafSize2(root.right);
        return leaf;
    }
    //(子问题思想)获取二叉树的高度
    public int height(TreeNode root){
        //所有左子树，右字树更高+1 为二叉树高度
        if(root==null){
            return 0;
        }
        int left=height( root.left);//所有左字数高度
        int right=height(root.right);//所有右字数高度

        return Integer.max(left,right)+1;//求左右字树更高的加根 即左加右加1为高
    }
    //(递归思想)求第K层叶子结点个数
    public int kLeafSize(TreeNode root ,int k){
        //第K层结点个数是依靠第K-1层左右孩子相加
        //注意当K=1时，没有K-1层，只有一个根，直接返回1
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int left=kLeafSize(root.left , k-1);
        int right=kLeafSize(root.right , k-1);
        return left+right;
    }
    //检测二叉树中是否有某元素
    public boolean contain(TreeNode root,int target){
        if(root==null){
            return false;
        }
        //到根找
        if(root.val!=target){
            return true;
        }
        //找左子树找
        if(contain(root.left,target)){
            return true;
        }
        //到右子树中找
        return contain(root.right,target);
    }
    //查找某个元素在二叉树中所在的结点
    public TreeNode nodeOf(TreeNode root,int target){
        if(root==null){
            return null;
        }
        //到根找
        if(root.val==target){
            return root;
        }
        //到左子树找
        TreeNode leftResult=nodeOf(root.left,target);
        if(leftResult!=null){
            return leftResult;
        }
        TreeNode rightResult=nodeOf(root.left,target);
        return rightResult;

    }
    //查找二叉树中是否存在某个结点
    public  boolean containNode(TreeNode root,TreeNode target){
        if(root==null){
            return false;
        }
        //到根找
        if(root==target){
            return true;
        }
        //到左子树找
        boolean leftResult= containNode( root.left,target);
        if(leftResult){
            //若左子树查找的结果为true,则返回总结果true
            return true;
        }
        //到右子树找
        boolean rightResult=containNode(root.right,target);
        //查找后返回总结果
        return rightResult;
    }
    //二叉树的层序遍历,不用将null打印
    public  void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            System.out.println(node.val);
            if (node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }
    //二叉树层序遍历，若是空树，将空作为"#"打印出来
    public void levelWithNull(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        //不用判断是否是空 直接放入队列
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node==null){
                System.out.println("#");
            }else{
                System.out.println(node.val+"  ");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
    }
    //判断一颗树是否是完全二叉树
    public  boolean isCompleteTree(TreeNode root){
        //用队列判断是否是完全二叉树
        Queue<TreeNode> queue=new LinkedList<>();
        //不管头是不是为空，直接放入队列
        queue.offer(root);
        //开启循环
        while (true){
           TreeNode node= queue.poll();
           //拿出队列首
           if(node==null){
               //如果为空 跳出循环 判断后面是否为空
               break;
           }
           //如果不为空 把左右字数拉进去
           queue.offer(node.left);
           queue.offer(node.right);
        }
        //队列不为空时判断后面是否还有非空结点出现，若有，不是完全二叉树
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node!=null){
                //有非空 返回 false
                return false;
            }
        }
        return true;
    }


}
